package oj;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author 郝文雪
 * @date 2022/8/26 17:03
 * @Description Test
 */
public class LC994{
    //bfs
    public int orangesRotting(int[][] grid) {
        int[][] dire={{1,0},{0,1},{-1,0},{0,-1}};
        Queue<int[]> q=new LinkedList<>();
        int count=0;//新鲜橘子的数量
        int n=grid.length;
        int m=grid[0].length;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]==1){
                    count++;
                }else if(grid[i][j]==2){
                    q.offer(new int[]{i,j});
                }
            }
        }
        int round=0;//最小的分钟数
        while(count>0 && !q.isEmpty()){
            round++;
            int k=q.size();
            for(int i=0;i<k;i++){
                int[] arr=q.poll();
                for(int j=0;j<4;j++){
                    int x=arr[0]+dire[j][0];
                    int y=arr[1]+dire[j][1];
                    if(x>=0 && x<n && y>=0 && y<m && grid[x][y]==1){
                        grid[x][y]=2;
                        count--;
                        q.offer(new int[]{x,y});
                    }
                }
            }

        }
        if(count>0){
            return -1;
        }else{
            return round;
        }
    }



    //dfs
//    int[][] dire={{1,0},{0,1},{-1,0},{0,-1}};
//    public int orangesRotting(int[][] grid) {
//        if(grid.length==0){
//            return 0;
//        }
//        for(int i=0;i<grid.length;i++){
//            for(int j=0;j<grid[0].length;j++){
//                if(grid[i][j]==2){
//                    dfs(grid,i,j,2);
//                }
//            }
//        }
//        int maxTime=0;
//        for(int i=0;i<grid.length;i++){
//            for(int j=0;j<grid[0].length;j++){
//                if(grid[i][j]==1){
//                    return -1;
//                }else{
//                    maxTime=Math.max(grid[i][j],maxTime);
//                }
//            }
//        }
//        return maxTime==0?0:maxTime-2;
//    }
//    private void dfs(int[][] grid,int x,int y,int time){
//        if(x<0 || x>=grid.length || y<0 || y>=grid[0].length){
//            return;
//        }
//        if(grid[x][y]!=1 && grid[x][y]<time) return;
//        grid[x][y]=time;
//        for(int k=0;k<4;k++){
//            int i=x+dire[k][0];
//            int j=y+dire[k][1];
//            dfs(grid,i,j,time+1);
//        }
//    }
}
